给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
思路及分析
使用『滑动窗口』
- 设置『滑动窗口』边界
left=right=0
; - 移动右边界,使其满足题目条件(不含有重复字符的 最长子串)
题目是求长度,那么就设置一个size
变量保存
在右边界移动的过程中,只要没出现重复元素就一直右移
当出现重复元素时,size
记录长度
之后,左边界收缩直到没有重复元素为止
现在的重点转换成: 如何判断滑动窗口内有重复元素
可以用一个列表来记录当前滑动窗口的所有元素
代码
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
if not s:
return 0
# 窗口左边界
left = 0
# 当前子串长度
cur_len = 0
# 子串最长长度
max_len = 0
lookup = []
n = len(s)
# i 表示窗口右边界
for i in range(n):
cur_len += 1 # 子串长度增加
while s[i] in lookup: # 检查右边界元素是否已经存在
lookup.remove(s[left]) # 收缩左边界
left += 1 # 收缩左边界
cur_len -= 1 # 子串长度减1
max_len = max(max_len, cur_len)
lookup.append(s[i])
return max_len